package problem;

//股票价格浮动，最大利益算法
//注意，股票只有在买入后才能卖出

/**
 * 叠高峰原理，dp[i],每一次存储最现在小值的差值
 */

public class MaxProfit {

    //情况：最小股价在最大股价之前
    public static int findMaxProfit(int[] array) {
        int maxPt = 0;
        int maxValue = array[0];
        int minValue = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] < minValue) {
                minValue = array[i];
            }
            if (array[i] > maxValue) {
                maxValue = array[i];
            }
        }
        maxPt = maxValue - minValue;
        return maxPt;
    }

    //股票收益 = 卖出价格 - 买入价格
    //买入价格需要小于卖出价格，最大收益为，最低价格买入，最高价格卖出
    public static int getMaxProfit(int[] prices) {
        //参数初始化
        //minValue表示，当前状态股票最低价格
        //maxProfit表示，整段日历中最高收益
        //prices[]价格表
        //profit[]收益表
        int minValue = prices[0];
        int maxProfit = 0;
        int[] profit = new int[prices.length];

        //动态记录收益表数据
        for (int i = 0; i < prices.length; i++) {
            //更新股票最低价格
            if (prices[i] < minValue) {
                minValue = prices[i];
            }
            //记录当前收益，(今日股价 - 当前股票低价)
            profit[i] = prices[i] - minValue;
        }

        //根据收益表，寻找出最大收益
        for (int i : profit) {
            if (i > maxProfit) {
                maxProfit = i;
            }
        }

        return maxProfit;
    }

}
